#include <iostream>
#include <vector>

#include <yaml-cpp/yaml.h>

#include "../include/sqstack.hpp"

/**
 * @brief 求栈的所有可能输出序列 
 * @param input 输入序列
 * @param index 表示当前是第几个输入
 * @param N 总共有N个输入
 * @param seq 某一个输出序列
 * @param result 存储所有序列
 */
void stack_simulation(
  std::vector<int> input,
  int index,
  int N,
  my_data::SqStack &stack, 
  std::vector<int> &seq,
  std::vector<std::vector<int>> &result)
{
  if(index == N)
  {
    // 输入序列全部入栈完毕，只能出栈
    // 将栈中的元素添加的seq后面，保存seq
    if(!stack.empty())
    {
      int top = stack.pop();
      seq.push_back(top);
      // 递归
      stack_simulation(input, index, N, stack, seq, result);
      // 回溯
      stack.push(top);
      seq.pop_back();
    }
    else
    {// 当前栈已空, 保存结果
      result.push_back(seq);
    }
  }
  else
  {
    // 先模拟要入栈的情况，再模拟要出栈的情况
    stack.push(input[index]);
    // 递归模拟本次入栈
    stack_simulation(input, index+1, N, stack, seq, result);
    stack.pop();

    // 递归模拟本次出栈
    if(!stack.empty())
    {
      int top = stack.pop();
      seq.push_back(top);
      stack_simulation(input, index, N, stack, seq, result);
      // 恢复序列和栈的状态
      seq.pop_back();
      stack.push(top);
    }
  }
}


int main()
{
  YAML::Node data_file;
    try
    {
      data_file = YAML::LoadFile("../data/Data.yaml");
    }
    catch(const std::exception& e)
    {
      std::cerr << e.what() << '\n';
    }
    
    int test_number = data_file["Stack"]["number"].as<int>();
    std::vector<int> input;
    for(int i=1; i<=test_number; ++i)
    {
      input.push_back(i);
    }
    std::vector<int> seq;
    std::vector<std::vector<int>> result;
    my_data::SqStack stack(test_number+1);
    std::cout<<"n = "<<test_number<<"的结果如下:\n";
    stack_simulation(input, 0, test_number, stack, seq, result);
    for(auto seq_i : result)
    {
      for(auto i : seq_i)
      { 
        std::cout<<i<<" ";
      }
      std::cout<<std::endl;
    }
}
